﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Samples.Trees.BinaryTree
{
    // http://en.wikipedia.org/wiki/Tree_traversal
    // Pre, In, Post are DepthFirst Traversal Techniques; Can be performed recursively or iteratively
    public class Traversals
    {
        //Used for BFS
        private static readonly Queue<Node> queue = new Queue<Node>();

        public static void PreOrder(Node node)
        {
            if (node == null) return;
            Console.WriteLine(node.Data);
            PreOrder(node.Left);
            PreOrder(node.Right);
        }

        // Symmetric Traversal
        public static void InOrder(Node node)
        {
            if (node == null) return;
            InOrder(node.Left);
            Console.WriteLine(node.Data);
            InOrder(node.Right);
        }

        public static void PostOrder(Node node)
        {
            if (node == null) return;
            PostOrder(node.Left);
            PostOrder(node.Right);
            Console.WriteLine(node.Data);
        }

        //level order traversal
        public static void BFS(Node node)
        {
            if (node == null) return;
            Console.WriteLine(node.Data);

            queue.Enqueue(node.Left);
            queue.Enqueue(node.Right);

            if (queue.Count != 0)
            {
                BFS(queue.Dequeue());
            }

        }
    }
}
